Sparsely populated data sets are utilized in numerous technical fields. The present invention was developed for efficiently encoding image data that has been transformed by successive applications of wavelet transforms, but is equally applicable to other types of sparsely populated data sets. Image data that has been transformed by successive applications of wavelet transforms tends to have large portions occupied by zero and near-zero values, especially if the data is subjected to a data quantization step prior to encoding.
The primary goals of the present invention are to provide an encoding methodology that (A) efficiently locates subarrays that are entirely occupied by zero data and encoding such subarrays with as few data bits as possible, (B) determines the maximum number of data bits required to encode subarrays that include at least some non-zero data, and (C) encodes non-zero data with the minimum number of data bits required to losslessly store such data.
Other goals of the present invention are to provide an encoding methodology that is computationally very efficient, and one that is suitable for implementation in hardware (i.e., electronic circuitry).